package com.markus.code.动态规划;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/16 16:06
 * todo: 蛇形路径
 */
public class Class03_SnackPath {
    /**
     * 给定一个二维数组matrix，每个单元都是一个整数，有正有负。最开始的时候小Q操纵 一条
     * 长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图，蛇每次只能够到达当前位置的右上
     * 相邻，右侧相邻和右下相邻的单元格。蛇蛇到达一个单元格后，自身的长度会瞬间加上该单
     * 元格的数值，任何情况下长度为负则游戏结束。小Q是个天才，他拥有一个超能力，可以在
     * 游戏开始的时候把地图中的某一个节点的值变为其相反数(注:最多 只能改变一个节点)。问
     * 在小Q游戏过程中，他的蛇蛇最长长度可以到多少?
     */
    public int snackPath(int [][]matrix){
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int resMax = Integer.MIN_VALUE;
        for (int i=0;i < matrix.length;i++){
            for (int j=0;j<matrix[i].length;j++){
                Info info = process(matrix,i,j);
                int ans = Math.max(info.noBest,info.yesBest);
                resMax = Math.max(ans, resMax);
            }
        }
        return resMax;
    }
    public static class Info{
        //一路走来，我没用过超能力
        public int noBest;
        //一路走来，我用过超能力
        public int yesBest;
        public Info(int noBest,int yesBest){
            this.noBest = noBest;
            this.yesBest = yesBest;
        }
    }
    private Info process(int [][]matrix,int i,int j){
        //基础条件：说明来到了第一列
        if (j==0){
            return new Info(matrix[i][j],-matrix[i][j]);
        }
        int noBest = -1;
        int yesBest = -1;
        Info leftUp = null;
        Info left = null;
        Info leftDown = null;
        //这时候就来到一定有左列的情况了,根据条件得出相应的左边一列的相关情况
        if (i-1 >= 0){
            leftUp = process(matrix,i-1,j-1);
        }
        left = process(matrix,i,j-1);
        if (i+1 < matrix.length){
            leftDown = process(matrix,i+1,j-1);
        }
        if (leftUp != null && leftUp.noBest >= 0){
            noBest = Math.max(leftUp.noBest+matrix[i][j],noBest);
            //再来计算一下我当前需要使用一下超能力的情况，前提是一路走来，并没有使用过这个能力
            yesBest = Math.max(leftUp.noBest-matrix[i][j],yesBest);
        }
        if (left != null && left.noBest >= 0){
            noBest = Math.max(left.noBest+matrix[i][j],noBest);
            yesBest = Math.max(left.noBest-matrix[i][j],yesBest);
        }
        if (leftDown != null && left.noBest >= 0){
            noBest = Math.max(leftDown.noBest+matrix[i][j],noBest);
            yesBest = Math.max(leftDown.noBest-matrix[i][j],yesBest);
        }
        //前面算完了之前没有使用过超能力的前提当前元素不使用超能力和使用超能里的情况，
        // 下面来解决一下之前使用过超能力，现在不能使用超能力的情况
        if (leftUp != null && leftUp.yesBest >= 0){
            yesBest = Math.max(leftUp.yesBest+matrix[i][j],yesBest);
        }
        if (left != null && left.yesBest >= 0){
            yesBest = Math.max(left.yesBest+matrix[i][j],yesBest);
        }
        if (leftDown != null && leftDown.yesBest >= 0){
            yesBest = Math.max(leftDown.yesBest+matrix[i][j],yesBest);
        }
        return new Info(noBest,yesBest);
    }

    public static void main(String[] args) {
        int [][]matrix = {{1,-4,10},{3,-2,-1},{2,-1,0},{0,5,2}};
        Class03_SnackPath demo = new Class03_SnackPath();
        System.out.println(demo.snackPath(matrix));
    }
}
